import time
import copy
import threading
import tkinter as tk
from tkinter import ttk
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
import numpy as np
from generator import generate_test_cases
from alg import insertion_sort, bubble_sort, quick_sort, heap_sort, is_sorted

# 设置matplotlib中文字体
plt.rcParams['font.sans-serif'] = ['SimHei']  # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False  # 用来正常显示负号

class SortingVisualizer:
    def __init__(self, root):
        self.root = root
        self.root.title("排序算法性能比较")
        self.root.geometry("1400x800")
        
        # 创建主框架
        self.main_frame = ttk.Frame(self.root)
        self.main_frame.pack(fill=tk.BOTH, expand=True, padx=10, pady=10)
        
        # 创建左侧面板（控制面板和结果显示）
        self.left_panel = ttk.Frame(self.main_frame)
        self.left_panel.pack(side=tk.LEFT, fill=tk.Y, padx=5, pady=5)
        
        # 创建控制面板
        self.create_control_panel()
        
        # 创建结果显示区域
        self.create_results_area()
        
        # 创建图表区域
        self.create_plot_area()
        
        # 创建状态栏
        self.status_var = tk.StringVar()
        self.status_var.set("就绪")
        self.status_bar = ttk.Label(self.root, textvariable=self.status_var, relief=tk.SUNKEN)
        self.status_bar.pack(side=tk.BOTTOM, fill=tk.X)
        
        # 初始化结果存储
        self.results = None

    def create_control_panel(self):
        """创建控制面板"""
        control_frame = ttk.LabelFrame(self.left_panel, text="控制面板")
        control_frame.pack(fill=tk.X, padx=5, pady=5)
        
        # 运行测试按钮
        self.run_button = ttk.Button(control_frame, text="运行测试", command=self.run_tests)
        self.run_button.pack(pady=5, padx=5, fill=tk.X)
        
        # 图表类型选择
        ttk.Label(control_frame, text="选择图表类型:").pack(pady=(10,5))
        self.plot_type = tk.StringVar(value="all")
        plot_types = [
            ("所有比较", "all"),
            ("运行时间比较", "runtime"),
            ("时间复杂度理论", "complexity"),
            ("比较次数", "comparisons"),
            ("交换次数", "swaps")
        ]
        for text, value in plot_types:
            ttk.Radiobutton(control_frame, text=text, value=value, 
                           variable=self.plot_type, 
                           command=self.update_plot).pack(anchor=tk.W, padx=5)

    def create_results_area(self):
        """创建结果显示区域"""
        results_frame = ttk.LabelFrame(self.left_panel, text="测试结果")
        results_frame.pack(fill=tk.BOTH, expand=True, padx=5, pady=5)
        
        # 创建文本框和滚动条
        self.results_text = tk.Text(results_frame, wrap=tk.WORD, width=40, height=20)
        scrollbar = ttk.Scrollbar(results_frame, orient=tk.VERTICAL, command=self.results_text.yview)
        self.results_text.configure(yscrollcommand=scrollbar.set)
        
        # 放置文本框和滚动条
        self.results_text.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)
        scrollbar.pack(side=tk.RIGHT, fill=tk.Y)

    def create_plot_area(self):
        """创建图表区域"""
        self.plot_frame = ttk.LabelFrame(self.main_frame, text="性能比较图表")
        self.plot_frame.pack(side=tk.RIGHT, fill=tk.BOTH, expand=True, padx=5, pady=5)
        
        # 创建matplotlib图形
        self.fig = plt.Figure(figsize=(8, 6))
        self.canvas = FigureCanvasTkAgg(self.fig, master=self.plot_frame)
        self.canvas.get_tk_widget().pack(fill=tk.BOTH, expand=True)

    def update_results_display(self, results):
        """更新结果显示"""
        self.results_text.delete(1.0, tk.END)
        for case_name, case_results in results.items():
            self.results_text.insert(tk.END, f"\n测试用例: {case_name}\n")
            self.results_text.insert(tk.END, "-" * 40 + "\n")
            
            for algo_name, result in case_results.items():
                self.results_text.insert(tk.END, f"\n{algo_name}:\n")
                self.results_text.insert(tk.END, f"  正确性: {'✓' if result['is_correct'] else '✗'}\n")
                self.results_text.insert(tk.END, f"  运行时间: {result['execution_time']:.6f} 秒\n")
                self.results_text.insert(tk.END, f"  比较次数: {result['comparisons']}\n")
                self.results_text.insert(tk.END, f"  交换次数: {result['swaps']}\n")
                self.results_text.insert(tk.END, f"  时间复杂度: {result['time_complexity']}\n")
            
            self.results_text.insert(tk.END, "\n" + "=" * 40 + "\n")

    def run_tests(self):
        """运行测试"""
        self.run_button.config(state='disabled')
        self.status_var.set("正在运行测试...")
        self.results_text.delete(1.0, tk.END)
        self.results_text.insert(tk.END, "正在运行测试，请稍候...\n")
        
        def run():
            self.results = run_all_tests()
            self.root.after(0, lambda: self.update_results_display(self.results))
            self.root.after(0, self.update_plot)
            self.root.after(0, lambda: self.run_button.config(state='normal'))
            self.root.after(0, lambda: self.status_var.set("测试完成"))
        
        threading.Thread(target=run, daemon=True).start()

    def update_plot(self):
        """更新图表"""
        if not self.results:
            return
            
        self.fig.clear()
        plot_type = self.plot_type.get()
        
        if plot_type == "all":
            self.plot_all_comparisons()
        elif plot_type == "runtime":
            self.plot_runtime_comparison()
        elif plot_type == "complexity":
            self.plot_complexity_theory()
        elif plot_type == "comparisons":
            self.plot_comparisons()
        elif plot_type == "swaps":
            self.plot_swaps()
            
        self.canvas.draw()

    def plot_all_comparisons(self):
        """绘制所有比较图表"""
        test_cases = list(self.results.keys())
        algorithms = list(self.results[test_cases[0]].keys())
        
        # 创建2x2的子图
        gs = self.fig.add_gridspec(2, 2)
        
        # 1. 运行时间比较
        ax1 = self.fig.add_subplot(gs[0, 0])
        x = np.arange(len(test_cases))
        width = 0.2
        for i, algo in enumerate(algorithms):
            times = [self.results[case][algo]['execution_time'] for case in test_cases]
            ax1.bar(x + i*width, times, width, label=algo)
        ax1.set_title('各算法运行时间比较')
        ax1.set_xticks(x + width*1.5)
        ax1.set_xticklabels(test_cases, rotation=45)
        ax1.legend()
        
        # 2. 时间复杂度理论
        ax2 = self.fig.add_subplot(gs[0, 1])
        n = np.linspace(1, 10000, 100)
        ax2.plot(n, n**2, label='O(n²)', linestyle='--')
        ax2.plot(n, n*np.log2(n), label='O(n log n)', linestyle='-.')
        ax2.plot(n, n, label='O(n)', linestyle=':')
        ax2.set_title('时间复杂度理论曲线')
        ax2.legend()
        
        # 3. 比较次数
        ax3 = self.fig.add_subplot(gs[1, 0])
        for i, algo in enumerate(algorithms):
            comparisons = [self.results[case][algo]['comparisons'] for case in test_cases]
            ax3.bar(x + i*width, comparisons, width, label=algo)
        ax3.set_title('比较次数')
        ax3.set_xticks(x + width*1.5)
        ax3.set_xticklabels(test_cases, rotation=45)
        ax3.legend()
        
        # 4. 交换次数
        ax4 = self.fig.add_subplot(gs[1, 1])
        for i, algo in enumerate(algorithms):
            swaps = [self.results[case][algo]['swaps'] for case in test_cases]
            ax4.bar(x + i*width, swaps, width, label=algo)
        ax4.set_title('交换次数')
        ax4.set_xticks(x + width*1.5)
        ax4.set_xticklabels(test_cases, rotation=45)
        ax4.legend()
        
        self.fig.tight_layout()

    def plot_runtime_comparison(self):
        """绘制运行时间比较"""
        ax = self.fig.add_subplot(111)
        test_cases = list(self.results.keys())
        algorithms = list(self.results[test_cases[0]].keys())
        
        x = np.arange(len(test_cases))
        width = 0.2
        for i, algo in enumerate(algorithms):
            times = [self.results[case][algo]['execution_time'] for case in test_cases]
            ax.bar(x + i*width, times, width, label=algo)
        
        ax.set_title('各算法运行时间比较')
        ax.set_xticks(x + width*1.5)
        ax.set_xticklabels(test_cases, rotation=45)
        ax.legend()
        self.fig.tight_layout()

    def plot_complexity_theory(self):
        """绘制时间复杂度理论曲线"""
        ax = self.fig.add_subplot(111)
        n = np.linspace(1, 10000, 100)
        
        ax.plot(n, n**2, label='O(n²)', linestyle='--')
        ax.plot(n, n*np.log2(n), label='O(n log n)', linestyle='-.')
        ax.plot(n, n, label='O(n)', linestyle=':')
        
        ax.set_title('时间复杂度理论曲线')
        ax.set_xlabel('数据规模 (n)')
        ax.set_ylabel('操作次数')
        ax.legend()
        self.fig.tight_layout()

    def plot_comparisons(self):
        """绘制比较次数"""
        ax = self.fig.add_subplot(111)
        test_cases = list(self.results.keys())
        algorithms = list(self.results[test_cases[0]].keys())
        
        x = np.arange(len(test_cases))
        width = 0.2
        for i, algo in enumerate(algorithms):
            comparisons = [self.results[case][algo]['comparisons'] for case in test_cases]
            ax.bar(x + i*width, comparisons, width, label=algo)
        
        ax.set_title('比较次数')
        ax.set_xticks(x + width*1.5)
        ax.set_xticklabels(test_cases, rotation=45)
        ax.legend()
        self.fig.tight_layout()

    def plot_swaps(self):
        """绘制交换次数"""
        ax = self.fig.add_subplot(111)
        test_cases = list(self.results.keys())
        algorithms = list(self.results[test_cases[0]].keys())
        
        x = np.arange(len(test_cases))
        width = 0.2
        for i, algo in enumerate(algorithms):
            swaps = [self.results[case][algo]['swaps'] for case in test_cases]
            ax.bar(x + i*width, swaps, width, label=algo)
        
        ax.set_title('交换次数')
        ax.set_xticks(x + width*1.5)
        ax.set_xticklabels(test_cases, rotation=45)
        ax.legend()
        self.fig.tight_layout()

def test_sorting_algorithm(sort_func, arr):
    """测试单个排序算法"""
    # 创建数组的深拷贝
    test_arr = copy.deepcopy(arr)
    
    # 记录开始时间
    start_time = time.time()
    
    # 执行排序
    result = sort_func(test_arr)
    
    # 计算运行时间
    end_time = time.time()
    execution_time = end_time - start_time
    
    # 验证排序结果
    is_correct = is_sorted(result['sorted_array'])
    
    return {
        'is_correct': is_correct,
        'execution_time': execution_time,
        'comparisons': result['comparisons'],
        'swaps': result['swaps'],
        'time_complexity': result['time_complexity']
    }

def run_all_tests():
    """运行所有测试用例"""
    # 获取测试数据
    test_cases = generate_test_cases()
    
    # 定义要测试的排序算法
    sorting_algorithms = {
        'Insertion Sort': insertion_sort,
        'Bubble Sort': bubble_sort,
        'Quick Sort': quick_sort,
        'Heap Sort': heap_sort
    }
    
    # 存储测试结果
    results = {}
    
    # 对每个测试用例运行所有排序算法
    for case_name, test_array in test_cases.items():
        print(f"\n测试用例: {case_name}")
        print(f"数组长度: {len(test_array)}")
        print("-" * 50)
        
        case_results = {}
        for algo_name, sort_func in sorting_algorithms.items():
            result = test_sorting_algorithm(sort_func, test_array)
            case_results[algo_name] = result
            
            print(f"{algo_name}:")
            print(f"  正确性: {'✓' if result['is_correct'] else '✗'}")
            print(f"  运行时间: {result['execution_time']:.6f} 秒")
            print(f"  比较次数: {result['comparisons']}")
            print(f"  交换次数: {result['swaps']}")
            print(f"  时间复杂度: {result['time_complexity']}")
        
        results[case_name] = case_results
    
    return results

def main():
    root = tk.Tk()
    app = SortingVisualizer(root)
    root.mainloop()

if __name__ == "__main__":
    main() 